package com.topcoder.tcos110;

public class YetAnotherRobotSimulation {
	public double getMaximumProbability(int L, int[] locationsX, int[] locationsY) {
		int N = locationsX.length;
		
		double[][] C = new double[L+1][L+1];
		C[0][0] = 1;
		for (int i=1; i<=L; i++) {
			C[0][i] = 1;
			for (int j=1; j<=i; j++) {
				C[j][i] = C[j][i-1] + C[j-1][i-1];
			}
		}
		
		double max = 0;
		for (int up=0; up<=L; up++) {
			for (int down=0; up+down<=L; down++) {
				for (int left=0; up+down+left<=L; left++) {
					int right = L - up - down - left;
					double p = 0;
					for (int i=0; i<N; i++) {
						p += probability(C, up, down, locationsX[i]) *
								probability(C, left, right, locationsY[i]);
					}
					max = Math.max(max, p);
				}
			}
		}
		
		return max;
	}
	
	private double probability(double[][] C, int p, int n, int t) {
		double r = 0;
		for (int i=0; i<=p; i++) {
			int j = i - t;
			if (j>=0 && j<=n) {
				r += C[i][p] * C[j][n] / (1L<<(p+n));
			}
		}
		return r;
	}
}
